class Solution {
public:
    vector<int> father;
    vector<int> size;

    int find(int i)
    {
        if (father[i] != i)
        {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    void set_union(int x, int y)
    {
        int fx = find(x), fy = find(y);
        if (fx != fy)
        {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }

    int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        father.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i++)
        {
            father[i] = i;
            size[i] = 1;
        }
        vector<int> factors(1e5 + 5, -1);
        for (int i = 0; i < n; i++)
        {
            int x = nums[i];
            for (int j = 2; j * j <= x; j++)
            {
                if (x % j == 0)
                {
                    if (factors[j] == -1)
                        factors[j] = i;
                    else
                        set_union(factors[j], i);

                    while (x % j == 0)
                        x /= j;
                }
            }
            if (x > 1)
            {
                if (factors[x] == -1)
                    factors[x] = i;
                else
                    set_union(factors[x], i);
            }
        }

        int ans = -1;
        for (int i = 0; i < n; i++)
        {
            if (size[i] > ans)
                ans = size[i];
        }
        return ans;
    }
};